#pragma once 
#include <iostream>
#include <vector>
using namespace std;

enum Status { EXIST, EMPTY, DELETE };

template<class K, class V>
struct HashData
{
  HashData()
    :_kv(make_pair(K(), V()))
    ,_status(EMPTY)
    {}
  pair<K, V> _kv;
  Status _status;
};


template<class K, class V>
class HashTable
{
  public:
  bool insert(const pair<K, V>& kv);
  HashData<K, V>* Find(const K& key);
  private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;
};

template<class K, class V>
bool HashTable<K, V>::insert(const pair<K, V>& kv)
{
  if (_tables.empty() || _n * 10 / _tables.size() >= 7)
  {
    //扩容
    size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
    HashTable<K, V> newHT;
    newHT._tables.resize(newSize);
    newHT._n = _n;
    for (size_t i = 0; i < _tables.size(); i++)
    {
      if (_tables[i]._status == EXIST)
      {
        newHT.insert(_tables[i]._kv);
      }
    }
    _tables.swap(newHT._tables);
  }
  size_t start = kv.first % _tables.size();
  size_t i = 0; 
  size_t index = start + i;
  while (_tables[index]._status == EXIST)
  {
    ++i;
    index = (start +  i) % _tables.size();
  }
  _tables[index]._kv = kv;
  _tables[index]._status = EXIST;
  _n++;
  return true;
}

template<class K, class V>
HashData<K, V>* HashTable<K,V>::Find(const K& key)
{

}
